package com.test.demo.algorithm.datastructure.linkedlist;

/**
 * 给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
 *
 * 给定一个链表: 1->2->3->4->5, 和 n = 2.
 * 当删除了倒数第二个节点后，链表变为 1->2->3->5.
 *
 *
 * 思路
 * 定义两个指针，如果删除倒数第N个，那么两个指针间隔就是N
 * 所以P1指针提前移动N次(2)，再循环P1指针，P2指针跟着移动
 * 直到P1.next不为空（P1=5,P2=3），也就是最后一个位置，那么P2指针间隔N个位置(P2=3),P2的后面一个元素就是倒数第N个位置，移除该元素
 *
 * P1会从头遍历到尾，时间复杂度是O(n),只用了常量级别的额外空间（P1和P2） 空间复杂度是O(1)
 */
public class RemoveNthFromEnd {
    private static Node removeNodeByEndNum(Node node, int n) {
        Node p1=node;
        Node p2=node;
        for (int i = 1; i <= n; i++) {
            p1 = p1.next;
        }
        while (p1.next!=null){
            p1 = p1.next;
            p2 = p2.next;
        }
        p2.next=p2.next.next;
        return node;
    }

    public static void main(String[] args) {
        //初始化node链表
        //1->2->3->4->5
        Node node = new Node(5);
        for (int i=4; i>0; i--){
            Node nodeTemp = new Node(i);
            nodeTemp.next = node;
            node = nodeTemp;
        }

        System.out.println("start_node-->"+node);
        node = removeNodeByEndNum(node, 3);
        System.out.println("end_node-->"+node);
    }
}


//Node节点
class Node{
    public Integer value;
    public Node next;

    public Node(Integer value) {
        this.value = value;
    }
    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                ", next=" + next +
                '}';
    }
}
